//You are given a string s and an array of strings words of the same length. Ret
//urn all starting indices of substring(s) in s that is a concatenation of each wo
//rd in words exactly once, in any order, and without any intervening characters. 
//
//
// You can return the answer in any order. 
//
// 
// Example 1: 
//
// 
//Input: s = "barfoothefoobarman", words = ["foo","bar"]
//Output: [0,9]
//Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" re
//spectively.
//The output order does not matter, returning [9,0] is fine too.
// 
//
// Example 2: 
//
// 
//Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
//Output: []
// 
//
// Example 3: 
//
// 
//Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
//Output: [6,9,12]
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 104 
// s consists of lower-case English letters. 
// 1 <= words.length <= 5000 
// 1 <= words[i].length <= 30 
// words[i] consists of lower-case English letters. 
// 
// Related Topics 哈希表 双指针 字符串 
// 👍 471 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Java：Substring with Concatenation of All Words
class P30SubstringWithConcatenationOfAllWords {
    public static void main(String[] args) {
        Solution solution = new P30SubstringWithConcatenationOfAllWords().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<Integer> list = new ArrayList<>();

        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> res = new ArrayList<>();
            Map<String, Integer> wordsMap = new HashMap<>();
            if (s.length() == 0 || words.length == 0) return res;
            for (String word : words) {
                // 主串s中没有这个单词，直接返回空
                if (s.indexOf(word) < 0) return res;
                // map中保存每个单词，和它出现的次数
                wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
            }
            // 每个单词的长度， 总长度
            int oneLen = words[0].length(), wordsLen = oneLen * words.length;
            // 主串s长度小于单词总和，返回空
            if (wordsLen > s.length()) return res;
            // 只讨论从0，1，...， oneLen-1 开始的子串情况，
            // 每次进行匹配的窗口大小为 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置
            for (int i = 0; i < oneLen; ++i) {
                // 左右窗口
                int left = i, right = i, count = 0;
                // 统计每个符合要求的word
                Map<String, Integer> subMap = new HashMap<>();
                // 右窗口不能超出主串长度
                while (right + oneLen <= s.length()) {
                    // 得到一个单词
                    String word = s.substring(right, right + oneLen);
                    // 有窗口右移
                    right += oneLen;
                    // words[]中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面
                    if (!wordsMap.containsKey(word)) {
                        left = right;
                        // 窗口内单词统计map清空，重新统计
                        subMap.clear();
                        // 符合要求的单词数清0
                        count = 0;
                    } else {
                        // 统计当前子串中这个单词出现的次数
                        subMap.put(word, subMap.getOrDefault(word, 0) + 1);
                        ++count;
                        // 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串
                        // 如 ["foo","bar","foo","the"]  "| foobarfoobar| foothe"
                        // 第二个bar虽然是words[]中的单词，但是次数抄了，那么右移一个单词长度后 "|barfoobarfoo|the"
                        // bar还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的bar和它之前的单词(串)全移出去
                        while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
                            // 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一)
                            String w = s.substring(left, left + oneLen);
                            subMap.put(w, subMap.getOrDefault(w, 0) - 1);
                            // 符合的单词数减一
                            --count;
                            // 左窗口位置右移
                            left += oneLen;
                        }
                        // 当前窗口字符串满足要求
                        if (count == words.length) res.add(left);
                    }
                }
            }
            return res;
        }

        public void getSort(int start, String[] words, String s) {
            if (start == words.length) {
                StringBuilder sb = new StringBuilder();
                for (String word : words) {
                    sb.append(word);
                }
                for (int i = 0; i < s.length(); i++) {
                    int index = s.indexOf(sb.toString(), i);
                    if (index != -1) {
                        if (!list.contains(index)) {
                            list.add(index);
                        }

                    }
                }

                return;
            } else {
                for (int i = start; i < words.length; i++) {
                    swap(start, i, words);
                    getSort(start + 1, words, s);
                    swap(start, i, words);
                }
            }
        }

        public void swap(int i, int j, String[] words) {
            String temp = words[i];
            words[i] = words[j];
            words[j] = temp;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}